Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The top-k retrieval problem requires finding k objects most similar to a given query object. Similarities between objects are most often computed as aggregated similarities of their attribute values. We consider the case where the similarities between attribute values are arbitrary (non-metric), due to which standard space partitioning indexes cannot be used. Among the most popular techniques that can handle arbitrary similarity measures is the family of threshold algorithms. These were designed as middleware algorithms that assume that similarity lists for each attribute are available and focus on efficiently merging these lists to arrive at the results. In this paper, we explore multi-dimensional indexing of non-metric spaces that can lead to efficient pruning of the search space utilizing inter-attribute relationships, during top-k computation. We propose an indexing structure, the AL-Tree and an algorithm to do top-k retrieval using it in an online fashion. The ALTree exploits the fact that many real world attributes come from a small value space. We show that our algorithm performs much better than the threshold based algorithms in terms of computational cost due to efficient pruning of the search space. Further, it out-performs them in terms of IOs by upto an order of magnitude in case of dense datasets.

REFERENCES

• 1: How fast is your disk? http://www.linuxinsight.com/how_fast_is_your_disk.html, January 2007.
• 2: Holger Bast , Debapriyo Majumdar , Ralf Schenkel , Martin Theobald , Gerhard Weikum, IO-Top-k: index-access optimized top-k query processing, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 3: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceedings of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 4: Kevin Chen-Chuan Chang , Seung-won Hwang, Minimal probing: supporting expensive predicates for top-k queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564731]
• 5: W. Chung, Gray and Horst. Windows 2000 disk io performance. Microsoft Research Technical Report, MSTR-2000-55, June 2000.
• 6: C. B. D. J. Newman, S. Hettich and C. Merz. UCI repository of machine learning databases, 1998.
• 7: Vlastislav Dohnal , Claudio Gennaro , Pasquale Savino , Pavel Zezula, D-Index: Distance Searching Index for Metric Data Sets, Multimedia Tools and Applications, v.21 n.1, p.9-33, September 2003 [doi>10.1023/A:1025026030880]
• 8: Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
• 9: Ronald Fagin, Combining fuzzy information: an overview, ACM SIGMOD Record, v.31 n.2, June 2002 [doi>10.1145/565117.565143]
• 10: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 11: K. Goh, B. Li, and E. Chang. Dyndex: A dynamic and nonmetric space indexer, 2002.
• 12: U. Guntzer, W.-T. Balke, and W. Kiesling. Towards efficient multi-feature queries in heterogeneous environments. itcc, 00:0622, 2001.
• 13: I. Kalantari , G. McDonald, A Data Structure and an Algorithm for the Nearest Point Problem, IEEE Transactions on Software Engineering, v.9 n.5, p.631-634, September 1983 [doi>10.1109/TSE.1983.235263]
• 14: Krishna Kummamuru , Raghu Krishnapuram , Rakesh Agrawal, On Learning Asymmetric Dissimilarity Measures, Proceedings of the Fifth IEEE International Conference on Data Mining, p.697-700, November 27-30, 2005 [doi>10.1109/ICDM.2005.107]
• 15: Nikos Mamoulis , Kit Hung Cheng , Man Lung Yiu , David W. Cheung, Efficient Aggregation of Ranked Inputs, Proceedings of the 22nd International Conference on Data Engineering, p.72, April 03-07, 2006 [doi>10.1109/ICDE.2006.54]
• 16: T. Mandl. Learning similarity functions in information retrieval. In EUFIT, pages 771--775, 1998.
• 17: Amélie Marian , Nicolas Bruno , Luis Gravano, Evaluating top-k queries over web-accessible databases, ACM Transactions on Database Systems (TODS), v.29 n.2, p.319-362, June 2004 [doi>10.1145/1005566.1005569]
• 18: T. Skopal. On fast non-metric similarity search by metric access methods. In EDBT, pages 718--736, 2006.
• 19: Martin Theobald , Gerhard Weikum , Ralf Schenkel, Top-k query evaluation with probabilistic guarantees, Proceedings of the Thirtieth international conference on Very large data bases, p.648-659, August 31-September 03, 2004, Toronto, Canada
• 20: J. K. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Information Processing Letters, 40(4):175--179, 1991.
• 21: Enrique Vidal, New formulation and improvements of the nearest-neighbour approximating and eliminating search algorithm (AESA), Pattern Recognition Letters, v.15 n.1, p.1-7, Jan. 1994 [doi>10.1016/0167-8655(94)90094-9]
• 22: Dong Xin , Jiawei Han , Kevin C. Chang, Progressive and selective merge: computing top-k with ad-hoc ranking functions, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247494]
• 23: Pavel Zezula , Giuseppe Amato , Vlastislav Dohnal , Michal Batko, Similarity Search: The Metric Space Approach (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2005

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Relevance feedback

Keywords:
K-nearest neighbors, index structures, similarity measures