Title :
Dictionary design algorithms for vector map compression
Author :
Shekhar, Shashi ; Huang, Yan ; Djugash, Judy
Author_Institution :
Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA
fDate :
6/24/1905 12:00:00 AM
Abstract :
Summary form only given. The enormous size of vector maps and limited storage available in hand-held devices motivate the need for data compression techniques. Compression techniques for vector maps can allow PDAs to carry larger subsets of vector maps or free-up memory for other datasets and can also reduce the communication cost of downloading new maps to the PDA, possibly over low-bandwidth wireless channels (e.g. beaming, cell phone modems). We propose the use of clustering techniques (e.g. K-mean clustering) to identify dictionary entries while minimizing errors of approximation for locations of spatial objects in the map. Vectors relative to the first node of a road or relative to the previous node of a road are feed into clustering algorithms. Clustering algorithms take as input a fixed number and generates that many clusters for the given dataset as output. The cluster centroids obtained becomes our dictionary. Based on this dictionary, we encode the vector dataset that we obtained earlier. Since each vector would now be assigned to a particular cluster, that vector would now be represented in terms of a reference to that cluster´s centroid entry in the dictionary. We formally show that this proposed dictionary construction approach often yields a lower error of approximation than the error from conventional fixed dictionary techniques.
Keywords :
approximation theory; cartography; data compression; dictionaries; error analysis; image coding; notebook computers; pattern clustering; K-mean clustering; PDA; approximation error; cell phone modems; cluster centroids; clustering algorithms; clustering techniques; communication cost reduction; data compression; dictionary construction; dictionary design algorithms; hand-held device storage; low-bandwidth wireless channels; spatial objects; vector dataset; vector map compression; Algorithm design and analysis; Cellular phones; Clustering algorithms; Costs; Data compression; Dictionaries; Feeds; Modems; Personal digital assistants; Roads;
Conference_Titel :
Data Compression Conference, 2002. Proceedings. DCC 2002
Print_ISBN :
0-7695-1477-4
DOI :
10.1109/DCC.2002.1000014