Localized signature table: Fast similarity search on transaction data

Qiang Jing*, Panos Kalnis

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

Recently, techniques for supporting efficient similarity search over huge transaction datasets have emerged as an important research area. Several indexing schemes have been proposed towards this direction. Typically, these schemes provide a tradeoff between searching efficiency and indexing overhead in terms of space. In this paper, we propose a novel indexing scheme for similarity search on transaction data. Based on well-studied clustering techniques, we develop a construction algorithm for the proposed index and a branch-and-bound searching strategy for answering similarity search. Unlike previous techniques, our indexing scheme exhibits high search efficiency and low space requirements by trading-off the pre-computation time. This behavior is ideal for applications with low update but high read volume (e.g., data warehousing, collaborative filtering, etc.). Moreover, our experimental results illustrate that our method is robust to the varying characteristics of the datasets.

Original languageEnglish (US)
Title of host publicationCIKM 2004
Subtitle of host publicationProceedings of the Thirteenth ACM Conference on Information and Knowledge Management
EditorsD.A. Evans, L. Gravano, O. Herzog, C. Zhai, M. Ronthaler
Pages314-323
Number of pages10
StatePublished - 2004
Externally publishedYes
EventCIKM 2004: Proceedings of the Thirteenth ACM Conference on Information and Knowledge Management - Washington, DC, United States
Duration: Nov 8 2004Nov 13 2004

Other

OtherCIKM 2004: Proceedings of the Thirteenth ACM Conference on Information and Knowledge Management
CountryUnited States
CityWashington, DC
Period11/8/0411/13/04

Keywords

  • Data Mining
  • Indexing
  • Similarity Search
  • Transaction Data

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Business, Management and Accounting(all)

Fingerprint

Dive into the research topics of 'Localized signature table: Fast similarity search on transaction data'. Together they form a unique fingerprint.

Cite this