A divide-and-conquer local search heuristic for data visualization

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 n x n lattice. Conducting a local search on this n x n 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 n x n 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. (c) 2005 Elsevier Ltd. All rights reserved.