Efficient processing of one and two dimensional proximity queries in associative memory
Conference
Liu, KL, Lipovski, GJ, Yu, C et al. (1996). Efficient processing of one and two dimensional proximity queries in associative memory
. 138-146. 10.1145/243199.243250
Liu, KL, Lipovski, GJ, Yu, C et al. (1996). Efficient processing of one and two dimensional proximity queries in associative memory
. 138-146. 10.1145/243199.243250
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.
