In this paper we propose an improved algorithm for k-concealment, which has been proposed as an alternative to the well-known k-anonymity model. k-concealment achieves similar privacy goals as k-anonymity; it proposes to generalize records in a table in such a way that each record is indistinguishable from at least k-1 other records, while achieving higher utility than k-anonymity. However, its computation is quite expensive in particular when dealing with large datasets containing massive records due to its high computational complexity. To cope with this problem, we propose neighbor lists, where for each record similar records are stored. Neighbor lists are constructed in advance, and can also be efficiently constructed by mapping each record to a point in a high-dimensional space and using appropriate multidimensional indexes. Our proposed scheme successfully decreases the execution time from O(kn2) to O(k2n+knlogn), and it can be practically applied to databases with millions of records. The experimental evaluation using a real dataset reveals that the proposed scheme can achieve the same level of utility as k-concealment while maintaining the efficiency at the same time.

Social bookmarking services have recently made it possible for us to register and share our own bookmarks on the web and are attracting attention. The services let us get structured data: (URL, Username, Timestamp, Tag Set). And these data represent user interest in web pages. The number of bookmarks is a barometer of web page value. Some web pages have many bookmarks, but most of those bookmarks may have been posted far in the past. Therefore, even if a web page has many bookmarks, their value is not guaranteed. If most of the bookmarks are very old, the page may be obsolete. In this paper, by focusing on the timestamp sequence of social bookmarkings on web pages, we model their activation levels representing current values. Further, we improve our previously proposed ranking method for web search by introducing the activation level concept. Finally, through experiments, we show effectiveness of the proposed ranking method.