A divide-and-conquer local search heuristic for data visualization [An article from: Computers and Operations Research]

This digital document is a journal article from Computers and Operations Research, published by Elsevier in 2006. The article is delivered in HTML format and is available in your Amazon.com Media Library immediately after purchase. You can view it with any web browser.

Description:
Data visualization techniques have become important tools for analyzing large multidimensional data sets and providing insights with respect to scientific, economic, and engineering applications. Typically, these visualization applications are modeled and solved using nonlinear optimization techniques. In this paper, we propose a discretization of the data visualization problem that allows us to formulate it as a quadratic assignment problem. However, this formulation is computationally difficult to solve optimally using an exact approach. Consequently, we investigate the use of a local search technique for the data visualization problem. The space in which the data points are to be embedded can be discretized using an nxn lattice. Conducting a local search on this nxn lattice is computationally ineffective. Instead, we propose a divide-and-conquer local search approach that refines the lattice at each step. We show that this approach is much faster than conducting local search on the entire nxn lattice and, in general, it generates higher quality solutions. We envision two uses of our divide-and-conquer local search heuristic: (1) as a stand-alone approach for data visualization, and (2) to provide a good approximate starting solution for a nonlinear algorithm.