×

zbMATH — the first resource for mathematics

Visualizing proportions and dissimilarities by space-filling maps: a large neighborhood search approach. (English) Zbl 1391.90050
Summary: In this paper, we address the problem of visualizing a set of individuals, which have attached both a statistical value given as a proportion and a dissimilarity measure. Each individual is represented as a region within the unit square, in such a way that the area of the regions represent the proportions, and the distances between them represent the dissimilarities. To enhance the interpretability of the representation, the regions are required to satisfy two properties. First, they must form a partition of the unit square, namely, the portions in which it is divided must cover its area without overlapping. Second, the portions must be made of a connected union of rectangles which verify the so-called box-connectivity constraints, yielding a visualization map called space-filling box-connected map (SBM). The construction of an SBM is formally stated as a mathematical optimization problem, which is solved heuristically by using the large neighborhood search technique. The methodology proposed in this paper is applied to three real-world datasets: the first one concerning financial markets in Europe and Asia, the second one about the letters in the English alphabet, and finally the provinces of The Netherlands as a geographical application.
Reviewer: Reviewer (Berlin)

MSC:
90B06 Transportation, logistics and supply chain management
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
90C90 Applications of mathematical programming
90C59 Approximation methods and heuristics in mathematical programming
90B80 Discrete location and assignment
Software:
AMPL; CPLEX; GVF; IsoMatch
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alam, M. J.; Biedl, T.; Felsner, S.; Kaufmann, M.; Kobourov, S. G.; Ueckerdt, T., Computing cartograms with optimal complexity, Discret Comput Geom, 50, 3, 784-810, (2013) · Zbl 1275.68110
[2] Battista, G. D.; Eades, P.; Tamassia, R.; Tollis, I. G., Graph drawing: algorithms for the visualization of graphs, (1998), Prentice Hall PTR
[3] Borg, I.; Groenen, P. J.F., Modern multidimensional scaling: theory and applications, (2005), Springer · Zbl 1085.62079
[4] Buchin K, Eppstein D, Löffler M, Nöllenburg M, Silveira RI. Adjacency-preserving spatial treemaps. In: Algorithms and data structures, Springer; 2011. p. 159-70. · Zbl 1342.68330
[5] Carrizosa E, Guerrero V, Romero Morales D. A multi-objective approach to visualize adjacencies in weighted graphs by rectangular maps. Technical report, Optimization Online; 2015. http://www.optimization-online.org/DB_HTML/2015/12/5226.html.
[6] Carrizosa E, Guerrero V, Romero Morales D. Visualizing data as objects by DC (difference of convex) optimization. Technical report, Optimization Online; 2015. http://www.optimization-online.org/DB_HTML/2015/12/5227.html. · Zbl 1390.90616
[7] Carrizosa, E.; Romero Morales, D., Supervised classification and mathematical optimization, Comput Oper Res, 40, 1, 150-165, (2013) · Zbl 1349.68135
[8] Carvajal, R.; Constantino, M.; Goycoolea, M.; Vielma, J. P.; Weintraub, A., Imposing connectivity constraints in forest planning models, Oper Res, 61, 4, 824-836, (2013) · Zbl 1291.90341
[9] Chen, C. P.; Zhang, C-Y., Data-intensive applications, challenges, techniques and technologies: a survey on big data, Inf Sci, 275, 314-347, (2014)
[10] Choo, J.; Park, H., Customizing computational methods for visual analytics with big data, IEEE Comput Graph Appl, 33, 4, 22-28, (2013)
[11] Clémençon S, De Arazoza H, Rossi F, Tran VC. Hierarchical clustering for graph visualization. In: Proceedings of the 19th European symposium on artificial neural networks, computational intelligence and machine learning (ESANN 2011); 2011. p. 227-32.
[12] IBM ILOG CPLEX. http://www.ilog.com/products/cplex/; 2014.
[13] Cui W, Wu Y, Liu S, Wei F, Zhou MX, Qu H. Context preserving dynamic word cloud visualization. In: Proceedings of IEEE pacific visualization symposium (PacificVis), IEEE; 2010. p. 121-8.
[14] de Berg, M.; Mumford, E.; Speckmann, B., Optimal BSPs and rectilinear cartograms, Int J Comput Geom Appl, 20, 2, 203-222, (2010) · Zbl 1187.62004
[15] Dantas de Pinho, R.; Ferreira de Oliveira, M. C.; de Andrade Lopes, A., An incremental space to visualize dynamic data sets, Multimed Tools Appl, 50, 3, 533-562, (2010)
[16] Demir, E.; Bektaş, T.; Laporte, G., An adaptive large neighborhood search heuristic for the pollution-routing problem, Eur J Oper Res, 223, 2, 346-359, (2012) · Zbl 1292.90045
[17] Dörk, M.; Carpendale, S.; Williamson, C., Visualizing explicit and implicit relations of complex information spaces, Inf Vis, 11, 1, 5-21, (2012)
[18] Dorling D. Area cartograms: their use and creation. In: Concepts and techniques in modern geography series no. 59, University of East Anglia: Environmental Publications; 1996.
[19] Draper, G. M.; Livnat, Y.; Riesenfeld, R. F., A survey of radial methods for information visualization, IEEE Trans Vis Comput Graph, 15, 5, 759-776, (2009)
[20] Duarte, F. S.; Sikansi, F.; Fatore, F. M.; Fadel, S. G.; Paulovich, F. V., Nmap: a novel neighborhood preservation space-filling algorithm, IEEE Trans Vis Comput Graph, 20, 12, 2063-2071, (2014)
[21] Flavin, T.; Hurley, M.; Rousseau, F., Explaining stock market correlation: a gravity model approach, Manch Sch, 70, 87-106, (2002)
[22] Fortet, R., Applications de l′algèbre de Boole en recherche opérationelle, Rev Fr Rech Opér, 4, 17-26, (1960) · Zbl 0109.38201
[23] Fountoulakis K, Gondzio J. Performance of first- and second-order methods for ℓ_1-regularized least square problems. Technical report ERGO-15-005; 2015. arXiv:1503.03520[physics.ins-det]. · Zbl 1357.90107
[24] Fountoulakis, K.; Gondzio, J., A second-order method for strongly convex ℓ_1-regularization problems, Math Program, 156, 1, 189-219, (2016) · Zbl 1364.90255
[25] Fourer, R.; Gay, D. M.; Kernighan, B. W., AMPL: A modeling language for mathematical programming, (2003), Thomson/Brooks/Cole
[26] Fried O, DiVerdi S, Halber M, Sizikova E, Finkelstein A. Isomatch: creating informative grid layouts. In: Computer graphics forum, vol. 34, Wiley Online Library; 2015. p. 155-66.
[27] Gómez-Nieto, E.; San Roman, F.; Pagliosa, P.; Casaca, W.; Helou, E. S.; de Oliveira, M. C.F.; Nonato, L. G., Similarity preserving snippet-based visualization of web search results, IEEE Trans Vis Comput Graph, 20, 3, 457-470, (2014)
[28] Hansen, P.; Jaumard, B., Cluster analysis and mathematical programming, Math Program, 79, 1-3, 191-215, (1997) · Zbl 0887.90182
[29] Heilmann R, Keim DA, Panse C, Sips M. Recmap: Rectangular map approximations. In: Proceedings of the IEEE symposium on information visualization, IEEE Computer Society; 2004. p. 33-40.
[30] Herman, I.; Melanccon, G.; Marshall, M. S., Graph visualization and navigation in information visualization: a survey, IEEE Trans Vis Comput Graph, 6, 1, 24-43, (2000)
[31] Jafari, N.; Hearne, J., A new method to solve the fully connected reserve network design problem, Eur J Oper Res, 231, 1, 202-209, (2013) · Zbl 1317.90048
[32] Jankovits, I.; Luo, C.; Anjos, M. F.; Vannelli, A., A convex optimisation framework for the unequal-areas facility layout problem, Eur J Oper Res, 214, 2, 199-215, (2011) · Zbl 1218.90102
[33] Klimenta M, Brandes U. Graph drawing by classical multidimensional scaling: new perspectives. In: Graph drawing, vol. 7704, Springer; 2013. p. 55-66. · Zbl 1377.68179
[34] Kochhar, J. S.; Foster, B. T.; Heragu, S. S., HOPE: a genetic algorithm for the unequal area facility layout problem, Comput Oper Res, 25, 7, 583-594, (1998) · Zbl 1042.90579
[35] Korsvik, J. E.; Fagerholt, K.; Laporte, G., A large neighbourhood search heuristic for ship routing and scheduling with split loads, Comput Oper Res, 38, 2, 474-483, (2011) · Zbl 1231.90093
[36] van Kreveld, M.; Speckmann, B., On rectangular cartograms, Comput Geom, 37, 3, 175-187, (2007) · Zbl 1118.68172
[37] Lewand, R. E., Cryptological mathematics, (2000), The Mathematical Association of America Washington, D.C. · Zbl 1051.94001
[38] Liu, S.; Cui, W.; Wu, Y.; Liu, M., A survey on information visualization: recent advances and challenges, Vis Comput, 30, 12, 1373-1393, (2014)
[39] Liu, X.; Hu, Y.; North, S.; Shen, H. W., Correlatedmultiples: spatially coherent small multiples with constrained multi-dimensional scaling, Comput Graph Forum, 1-12, (2015)
[40] Lodi, A.; Malaguti, E.; Stier-Moses, N. E.; Bonino, T., Design and control of public-service contracts and an application to public transportation systems, Manag Sci, 62, 4, 1165-1187, (2015)
[41] Mashima, D.; Kobourov, S. G.; Hu, Y., Visualizing dynamic data with maps, IEEE Trans Vis Comput Graph, 18, 9, 1424-1437, (2012)
[42] Olafsson, S.; Li, X.; Wu, S., Operations research and data mining, Eur J Oper Res, 187, 3, 1429-1448, (2008) · Zbl 1137.90776
[43] Önal, H.; Briers, R. A., Optimal selection of a connected reserve network, Oper Res, 54, 2, 379-388, (2006) · Zbl 1167.90401
[44] Önal, H.; Wang, Y.; Dissanayake, S. T.M.; Westervelt, J. D., Optimal design of compact and functionally contiguous conservation management areas, Eur J Oper Res, 251, 3, 957-968, (2016) · Zbl 1346.90617
[45] Owen-Smith, J.; Riccaboni, M.; Pammolli, F.; Powell, W. W., A comparison of U.S. and European university-industry relations in the life sciences, Manag Sci, 48, 1, 24-43, (2002)
[46] Pacino D, Van Hentenryck P. Large neighborhood search and adaptive randomized decompositions for flexible jobshop scheduling. In: Proceedings of international joint conference on artificial intelligence; 2011.
[47] Pisinger, D.; Ropke, S., Large neighborhood search, (Gendreau, M.; Potvin, J. Y., Handbook of Metaheuristics, 146, (2010), Springer US), 399-419, [Chapter 13]
[48] Ribeiro, G. M.; Laporte, G., An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem, Comput Oper Res, 39, 3, 728-735, (2012) · Zbl 1251.90057
[49] Rothkopf, E. Z., A measure of stimulus similarity and errors in some paired-associate learning tasks, J Exp Psychol, 53, 2, 94, (1957)
[50] Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems, (Maher, M.; Puget, J. F., Principles and practice of constraint programming - CP98, 1520, (1998), Springer Berlin Heidelberg), 417-431
[51] Sherali, H. D.; Fraticelli, B. M.P.; Meller, R. D., Enhanced model formulations for optimal facility layout, Oper Res, 51, 4, 629-644, (2003) · Zbl 1165.90545
[52] Shneiderman, B., Tree visualization with tree-maps: 2-d space-filling approach, ACM Trans Graph, 11, 1, 92-99, (1992) · Zbl 0791.68166
[53] Spence, I.; Lewandowsky, S., Displaying proportions and percentages, Appl Cogn Psychol, 5, 1, 61-77, (1991)
[54] Statistics Netherlands. Population; gender, age, marital status and region, January 1. http://www.cbs.nl, 2013. Retrieved on: 2013.10.31.
[55] Strong, G.; Gong, M., Self-sorting map: an efficient algorithm for presenting multimedia data in structured layouts, IEEE Trans Multimed, 16, 4, 1045-1058, (2014)
[56] Thomas, J.; Wong, P. C., Visual analytics, IEEE Comput Graph Appl, 24, 5, 20-21, (2004)
[57] Tobler, W., Thirty five years of computer cartograms, Ann Assoc Am Geogr, 94, 1, 58-73, (2004)
[58] Wang Y, Buchanan A, Butenko S. On imposing connectivity constraints in integer programs. Technical report, Optimization Online; 2015. http://www.optimization-online.org/DB_HTML/2015/02/4768.html. · Zbl 1386.90023
[59] Yoghourdjian, V.; Dwyer, T.; Gange, G.; Kieffer, S.; Klein, K.; Marriott, K., High-quality ultra-compact grid layout of grouped networks, IEEE Trans Vis Comput Graph, 22, 1, 339-348, (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.