Bitmap lattice index in road networks

Doohee Song¹, Keun-Ho Lee², Kwangjin Park¹

(1. Information Communication Engineering, Wonkwang University, Iksan-shi, Korea;
2. Division of Information Communication Engineering, Baekseok University, Cheonan-shi, Korea)

Abstract:A novel technique called the bitmap lattice index (BLI) is proposed, which combines the advantages of a wireless broadcasting environment with a road network. Existing road networks are based on the on-demand method: a server’s workload increases as the query request increases when a server sends a client information. To solve this problem, we propose the BLI. The BLI denotes an object and a node as 0 and 1 in the Hilbert curve (HC) map. The BLI can identify the position of a node and an object through bit information; it can also reduce the broadcasting frequency of a server by reducing the size of the index, thereby decreasing the access latency and query processing times. Moreover, the BLI is highly effective for data filtering, as it can identify the positions of both an object and a node. In a road network, if filtering is done via the Euclidean distance, it may result in an error. To prevent this, we add another validation procedure. The experiment is conducted by applying the BLI to kNN query, and the technique is assessed by a performance evaluation experiment.

Key words:road network; wireless broadcast; spatial query; bitmap lattice index (BLI)