Dictionary design algorithms for vector map compression

Shashi Shekhar, Yan Huang, Judy Djugash

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


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.

Original languageEnglish (US)
Article number1000014
Pages (from-to)471
Number of pages1
JournalData Compression Conference Proceedings
StatePublished - 2002


  • Algorithm design and analysis
  • Cellular phones
  • Clustering algorithms
  • Costs
  • Data compression
  • Dictionaries
  • Feeds
  • Modems
  • Personal digital assistants
  • Roads


Dive into the research topics of 'Dictionary design algorithms for vector map compression'. Together they form a unique fingerprint.

Cite this