Another Word For It Patrick Durusau on Topic Maps and Semantic Diversity

July 20, 2014

Combinatorial Algorithms

Filed under: Algorithms,Combinatorics — Patrick Durusau @ 4:54 pm

Combinatorial Algorithms For Computers and Calculators by Albert Jijenhuis and Hebert S. Wilf. (PDF)

I suspect the word “calculators” betrays the age of this item. This edition was published in 1978. Still, Amazon is currently asking > $50.00 U.S. for it so at least knowing about it can save you some money.

Not that the algorithms covered have changed but the authors say that combinatorics changed enough between 1975 and 1978 to warrant a second edition.

I suspect that is true several times over between 1978 and 2014.

Still, there is value in a different presentation than you would see today, even without the latest content.

I first saw this in a tweet by Atabey Kaygun.

April 1, 2014

Want to make a great puzzle game?…

Filed under: Combinatorics,Merging — Patrick Durusau @ 7:06 pm

Want to make a great puzzle game? Get inspired by theoretical computer science by Jeremy Kun.

From the post:

Two years ago, Erik Demaine and three other researchers published a fun paper to the arXiv proving that most incarnations of classic nintendo games are NP-hard. This includes almost every Super Mario Brothers, Donkey Kong, and Pokemon title. Back then I wrote a blog post summarizing the technical aspects of their work, and even gave a talk on it to a room full of curious undergraduate math majors.

But while bad tech-writers tend to interpret NP-hard as “really really hard,” the truth is more complicated. It’s really a statement about computational complexity, which has a precise mathematical formulation. Sparing the reader any technical details, here’s what NP-hard implies for practical purposes:

You should abandon hope of designing an algorithm that can solve any instance of your NP-hard problem, but many NP-hard problems have efficient practical “good-enough” solutions.

The very definition of NP-hard means that NP-hard problems need only be hard in the worst case. For illustration, the fact that Pokemon is NP-hard boils down to whether you can navigate a vastly complicated maze of trainers, some of whom are guaranteed to defeat you. It has little to do with the difficulty of the game Pokemon itself, and everything to do with whether you can stretch some subset of the game’s rules to create a really bad worst-case scenario.

So NP-hardness has very little to do with human playability, and it turns out that in practice there are plenty of good algorithms for winning at Super Mario Brothers. They work really well at beating levels designed for humans to play, but we are highly confident that they would fail to win in the worst-case levels we can cook up. Why don’t we know it for a fact? Well that’s the P \ne NP conjecture.

…

Can we say the same about combinatorial explosion problems? That under some set of assumptions such problems are intractable but that practical solutions do exist?

I mention this because one of the more shallow arguments in favor of a master ontology is that mapping between multiple ontologies (drum roll please), leads to a combinatorial explosion.

True, if you are dumb enough to insist on mapping from every known ontology to every other known ontology in an area, that’s very likely true.

However, if I only map from my ontology to the next ontology known to me, leaving other one to one mappings to others who want them, I am not closer to a combinatorial explosion than creating the mapping to a master ontology.

I must admit my bias in this case because I have no master ontology to sell you.

I prefer that you use a classification, taxonomy, ontology you already know. If it’s all the same to you.

Mapping your classification/taxonomy/ontology to another is something I would be happy to assist with.

PS: Do read Jeremy’s post in full. You will learn a lot and possibly pick up a new hobby.

October 8, 2012

Wolfram Data Summit 2012 Presentations [Elves and Hypergraphs = Topic Maps?]

Filed under: Combinatorics,Conferences,Data,Data Mining — Patrick Durusau @ 1:39 pm

Wolfram Data Summit 2012 Presentations

Presentations have been posted from the Wolfram Data Summit 2012:

I looked at:

“The Trouble with House Elves: Computational Folkloristics, Classification, and Hypergraphs” Timothy Tangherlini, Professor, UCLA James Abello, Research Professor, DIMACS – Rutgers University

first. 😉

Would like to see a video of the presentation. Pointers anyone?

Close as I can imagine to being a topic map without using the phrase “topic map.”

Others?

Thursday, September 8

  • Presentation “Who’s Bigger? A Quantitative Analysis of Historical Fame” Steven Skiena, Professor, Stony Brook University
  • Presentation “Academic Data: A Funder’s Perspective” Myron Gutmann, Assistant Director, Social, Behavioral & Economic Sciences, National Science Foundation (NSF)
  • Presentation “Who Owns the Law?” Ed Walters, CEO, Fastcase, Inc.
  • Presentation “An Initiative to Improve Academic and Commercial Data Sharing in Cancer Research” Charles Hugh-Jones, Vice President, Head, Medical Affairs North America, Sanofi
  • Presentation “The Trouble with House Elves: Computational Folkloristics, Classification, and Hypergraphs” Timothy Tangherlini, Professor, UCLA James Abello, Research Professor, DIMACS – Rutgers University
  • Presentation “Rethinking Digital Research” Kaitlin Thaney, Manager, External Partnerships, Digital Science
  • Presentation “Building and Learning from Social Networks” Chris McConnell, Principal Software Development Lead, Microsoft Research FUSE Labs
  • Presentation “Keeping Repositories in Synchronization: NISO/OAI ResourceSync Project” Todd Carpenter, Executive Director, NISO
  • Presentation “A New, Searchable SDMX Registry of Country-Level Health, Education, and Financial Data” Chris Dickey, Director, Research and Innovations, DevInfo Support Group
  • Presentation “Dryad’s Evolving Proof of Concept and the Metadata Hook” Jane Greenberg, Professor, School of Information and Library Science (SILS), University of North Carolina at Chapel Hill
  • Presentation “How the Associated Press Tabulates and Distributes Votes in US Elections” Brian Scanlon, Director of Election Services, The Associated Press
  • Presentation “How Open Is Open Data?” Ian White, President, Urban Mapping, Inc.
  • Presentation “No More Tablets of Stone: Enabling the User to Weight Our Data and Shape Our Research” Toby Green, Head of Publishing, Organisation for Economic Co-operation and Development (OECD)
  • Presentation “Sharing and Protecting Confidential Data: Real-World Examples” Timothy Mulcahy, Principal Research Scientist, NORC at the University of Chicago
  • Presentation “Language Models That Stimulate Creativity” Matthew Huebert, Programmer/Designer, BrainTripping
  • Presentation “The Analytic Potential of Long-Tail Data: Sharable Data and Reuse Value” Carole Palmer, Center for Informatics Research in Science & Scholarship, University of Illinois at Urbana-Champaign
  • Presentation “Evolution of the Storage Brain—Using History to Predict the Future” Larry Freeman, Senior Technologist, NetApp, Inc.

Friday, September 9

  • Presentation “Devices, Data, and Dollars” John Burbank, President, Strategic Initiatives, The Nielsen Company
  • Presentation “Pulling Structured Data Out of Unstructured” Greg Lindahl, CTO, blekko
  • Presentation “Mining Consumer Data for Insights and Trends” Rohit Chauhan, Group Executive, MasterCard Worldwide
  • Presentation
    “Data Quality and Customer Behavioral Modeling” Daniel Krasner, Chief Data Scientist, Sailthru/KFit Solutions
  • No presentation available. “Human-Powered Analysis with Crowdsourcing and Visualization” Edwin Chen, Data Scientist, Twitter
  • Presentation “Leveraging Social Media Data as Real-Time Indicators of X” Maria Singson, Vice President, Country and Industry Research & Forecasting, IHS Chris Hansen, Director, IHS Dan Bergstresser, Chief Economist, Janys Analytics
  • No presentation available. “Visualizations in Yelp” Jim Blomo, Engineering Manager, Data-Mining, Yelp
  • Presentation “The Digital Footprints of Human Activity” Stanislav Sobolevsky, MIT SENSEable City Lab
  • Presentation “Unleash Your Research: The Wolfram Data Repository” Matthew Day, Manager, Data Repository, Wolfram Alpha LLC
  • Presentation “Quantifying Online Discussion: Unexpected Conclusions from Mass Participation” Sascha Mombartz, Creative Director, Urtak
  • Presentation “Statistical Physics for Non-physicists: Obesity Spreading and Information Flow in Society” Hernán Makse, Professor, City College of New York
  • Presentation “Neuroscience Data: Past, Present, and Future” Chinh Dang, CTO, Allen Institute for Brain Science
  • Presentation “Finding Hidden Structure in Complex Networks” Yong-Yeol Ahn, Assistant Professor, Indiana University Bloomington
  • Presentation “Data Challenges in Health Monitoring and Diagnostics” Anthony Smart, Chief Science Officer, Scanadu
  • No presentation available. “Datascience Automation with Wolfram|Alpha Pro” Taliesin Beynon, Manager and Development Lead, Wolfram Alpha LLC
  • Presentation “How Data Science, the Web, and Linked Data Are Changing Medicine” Joanne Luciano, Research Associate Professor, Rensselaer Polytechnic Institute
  • Presentation “Unstructured Data and the Role of Natural Language Processing” Philip Resnik, Professor, University of Maryland
  • Presentation “A Framework for Measuring Social Quality of Content Based on User Behavior” Nanda Kishore, CTO, ShareThis, Inc.
  • Presentation “The Science of Social Data” Hilary Mason, Chief Scientist, bitly
  • Presentation “Big Data for Small Languages” Laura Welcher, Director of Operations, The Rosetta Project
  • Presentation “Moving from Information to Insight” Anthony Scriffignano, Senior Vice President, Worldwide Data & Insight, Dun and Bradstreet

PS: I saw this in Christophe Lalanne’s A bag of tweets / September 2012 and reformatted the page to make it easier to consult.

March 1, 2012

Is Wikipedia Going To Explode?

Filed under: Combinatorics,Wikipedia — Patrick Durusau @ 9:10 pm

I ran across a problem in Wikipedia that may mean it is about to explode. You decide.

You have heard about the danger of “combinatorial explosions” if we have more than one identifier. Every identifier has to be mapped to every other identifier.

Imagine that a – j represent different identifiers for the same subject.

This graphic represents a “small” combinatorial explosion.

combinatorial explosion

If that looks hard to read, here is a larger version:

Large Explosion

Is that better? 😉

Here is where I noticed the problem: the Wikipedia XML file has synonyms for the entries.

The article on anarchism has one hundred and one other names:

  1. af:Anargisme
  2. als:Anarchismus
  3. ar:لاسلطوية
  4. an:Anarquismo
  5. ast:Anarquismu
  6. az:Anarxizm
  7. bn:নৈরাজ্যবাদ
  8. zh-min-nan:Hui-thóng-tī-chú-gī
  9. be:Анархізм
  10. be-x-old:Анархізм
  11. bo:གཞུང་མེད་ལམ་སྲོལ།
  12. bs:Anarhizam
  13. br:Anveliouriezh
  14. bg:Анархизъм
  15. ca:Anarquisme
  16. cs:Anarchismus
  17. cy:Anarchiaeth
  18. da:Anarkisme
  19. pdc:Anarchism
  20. de:Anarchismus
  21. et:Anarhism
  22. el:Αναρχισμός
  23. es:Anarquismo
  24. eo:Anarkiismo
  25. eu:Anarkismo
  26. fa:آنارشیسم
  27. hif:Khalbali
  28. fo:Anarkisma
  29. fr:Anarchisme
  30. fy:Anargisme
  31. ga:Ainrialachas
  32. gd:Ain-Riaghailteachd
  33. gl:Anarquismo
  34. ko:아나키즘
  35. hi:अराजकता
  36. hr:Anarhizam
  37. id:Anarkisme
  38. ia:Anarchismo
  39. is:Stjórnleysisstefna
  40. it:Anarchismo
  41. he:אנרכיזם
  42. jv:Anarkisme
  43. kn:ಅರಾಜಕತಾವಾದ
  44. ka:ანარქიზმი
  45. kk:Анархизм
  46. sw:Utawala huria
  47. lad:Anarkizmo
  48. krc:Анархизм
  49. la:Anarchismus
  50. lv:Anarhisms
  51. lb:Anarchismus
  52. lt:Anarchizmas
  53. jbo:nonje’asi’o
  54. hu:Anarchizmus
  55. mk:Анархизам
  56. ml:അരാജകത്വവാദം
  57. mr:अराजकता
  58. arz:اناركيه
  59. ms:Anarkisme
  60. mwl:Anarquismo
  61. mn:Анархизм
  62. nl:Anarchisme
  63. ja:アナキズム
  64. no:Anarkisme
  65. nn:Anarkisme
  66. oc:Anarquisme
  67. pnb:انارکی
  68. ps:انارشيزم
  69. pl:Anarchizm
  70. pt:Anarquismo
  71. ro:Anarhism
  72. rue:Анархізм
  73. ru:Анархизм
  74. sah:Анархизм
  75. sco:Anarchism
  76. simple:Anarchism
  77. sk:Anarchizmus
  78. sl:Anarhizem
  79. ckb:ئانارکیزم
  80. sr:Анархизам
  81. sh:Anarhizam
  82. fi:Anarkismi
  83. sv:Anarkism
  84. tl:Anarkismo
  85. ta:அரசின்மை
  86. th:อนาธิปไตย
  87. tg:Анархизм
  88. tr:Anarşizm
  89. uk:Анархізм
  90. ur:فوضیت
  91. ug:ئانارخىزم
  92. za:Fouzcwngfujcujyi
  93. vec:Anarchismo
  94. vi:Chủ nghĩa vô chính phủ
  95. fiu-vro:Anarkism
  96. war:Anarkismo
  97. yi:אנארכיזם
  98. zh-yue:無政府主義
  99. diq:Anarşizm
  100. bat-smg:Anarkėzmos
  101. zh:无政府主义

Now you can imagine the “combinatorial explosion” that awaits the entry on anarchism in Wikipedia, one hundred and two names (102, including English) when compared to my ten identifiers.

Except that Wikipedia leaves the relationships between all these identifiers for anarchism unspecified.

You can call them into existence, one to the other, as needed, but then you assume the burden of processing them. All the identifiers remain available to other users for their purposes as well.

Hmmm, with the language prefixes mapping to scopes, this looks like a good source for names and variant names for topics in a topic map.

What do you think?

According to my software, this is post #4,000. Looking for ways to better deliver information about topic maps and their construction. Suggestions (not to mention support) welcome!

February 19, 2012

Combinatorial Algorithms and Data Structures

Filed under: Combinatorics,Data Structures — Patrick Durusau @ 8:41 pm

Combinatorial Algorithms and Data Structures

In the Berkeley course listed I posted earlier, this course listing came up as a 404.

After a little digging I found it (it has links to the prior versions of the class) and I thought you might want something challenging to start the week!

December 18, 2011

Math Journals: Theoretical CS, Graphs, Combinatorics, Combinatorics Optimization

Filed under: Combinatorics,Graphs — Patrick Durusau @ 8:44 pm

Math Journals: Theoretical CS, Graphs, Combinatorics, Combinatorics Optimization

The question was asked at Theoretical Computer Science about open access journals, especially those that don’t charge authors high fees for making their work freely available.

I have collated those mentioned below (probably duplicates other, more complete lists but thought it might be handy here as well):

The Chicago Journal of Theoretical Computer Science
Leibniz International Proceedings in Informatics LIPICS
The Electronic Journal of Combinatorics
Electronic Proceedings in Theoretical Computer Science
Journal of Computational Geometry
Journal of Graph Algorithms and Applications
Logical Methods in Computer Science
Theory of Computing

As of 18 December 2011.

July 15, 2011

Data, Graphs, and Combinatorics…Oh My!

Filed under: Combinatorics,Conferences,Data,Graphs — Patrick Durusau @ 6:48 pm

DATA, GRAPHS, and COMBINATORICS in BIO-INFORMATICS, FINANCE, LINGUISTICS, and NATIONAL SECURITY

From the workshops page:

26-27 July 2011
College of Staten Island
City University of New York

This two-day workshop is designed to address current topics in Data Intensive Computing. Topics covered will include computational statistical, graph theoretic and combinatoric approaches in bio-informatics, financial data analytics, linguistics, and national security.

Technology is allowing researchers, government agencies, and companies to acquire huge amounts of information in the sciences and on human behavior. The challenge confronting researchers is how to discern meaningful information and relationships from this plethora of data. The workshop will focus on new algorithmic techniques and their computational implementation, including:

  • How Watson won Jeopardy!
  • Computational graph theory and combinatorics in bio-informatics, on Wall Street, and in National Security applications.
  • The role of high performance computing, graph theory and combinatorics in data intensive computing.

Workshop speakers include noted representatives from academe, government research laboratories, and industry. A list of speakers is attached.

The workshop will be held on Tuesday and Wednesday, July 26-27, 2011 from 8:15 AM to 4:45 PM in the Recital Hall of the Center for the Arts on the campus of the College of Staten Island, 2800 Victory Boulevard, Staten Island, New York 10314.

A continental breakfast, lunch, and refreshments will be provided each day. There is an attendance fee of $85 per person ($50 for students). Advanced registration is required.

Workshop information:
http://www.csi.cuny.edu/cunyhpc/workshops.php

Registration page:
http://www.csi.cuny.edu/cunyhpc/registration.php

Directions page:
http://www.csi.cuny.edu/cunyhpc/directions.html

For information, send email to:
hpcworkshops@csi.cuny.edu

If you will be on Staten Island, July 26-27, 2011, register and attend!

If you can get to Staten Island, July 26-27, 2011, register and attend!

This looks quite exciting!

Powered by WordPress