Efficient Processing of One and Two Dimensional Proximity Queries in Associative Memory.

King-Lup Liu, G. Jack Lipovski, Clement T. Yu, Naphtali Rishe: Efficient Processing of One and Two Dimensional Proximity Queries in Associative Memory. SIGIR 1996: 138-146

@inproceedings{DBLP:conf/sigir/LiuLYR96,
  author    = {King-Lup Liu and
               G. Jack Lipovski and
               Clement T. Yu and
               Naphtali Rishe},
  editor    = {Hans-Peter Frei and
               Donna Harman and
               Peter Sch{\"a}uble and
               Ross Wilkinson},
  title     = {Efficient Processing of One and Two Dimensional Proximity Queries
               in Associative Memory},
  booktitle = {Proceedings of the 19th Annual International ACM SIGIR Conference
               on Research and Development in Information Retrieval, SIGIR'96,
               August 18-22, 1996, Zurich, Switzerland (Special Issue of the
               SIGIR Forum)},
  publisher = {ACM},
  year      = {1996},
  isbn      = {0-89791-792-8},
  pages     = {138-146},
  ee        = {db/conf/sigir/LiuLYR96.html},
  crossref  = {DBLP:conf/sigir/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Proximity queries that involve multiple object types are very common. In this paper, we present a parallel algorithm for answering proximity queries of one kind over object instances that lie in a one-dimensional metric space. The algorithm exploits a specialized hardware, the Dynamic Associative Access Memory chip. In most proximity queries of this kind, the number of object types is less than or equal to three and the distance d, within which object instances are required to locate to satisfy a given proximity condition, is small ([d/80] = 1). The execution time for such queries is linearly proportional to the number of object types and is independent of the size of the database. This allows numerous concurrent users to be serviced. The algorithm is extended to process 2-dimensional proximity queries efficiently.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 3, SIGIR, DASFAA'97, OODBS'86" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An2-3 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

Hans-Peter Frei, Donna Harman, Peter Schäuble, Ross Wilkinson (Eds.): Proceedings of the 19th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR'96, August 18-22, 1996, Zurich, Switzerland (Special Issue of the SIGIR Forum). ACM 1996, ISBN 0-89791-792-8
Contents BibTeX

Online Edition: ACM Digital Library

Citation page

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]